1. Technical Field of the Invention
The present invention relates to digital watermarks and, more particularly, to watermarks with values derived from remote platforms. In some embodiments, the watermarks are used in connection with multiple levels of indirection.
2. Background Art
Processor serial numbers (PSNs) are numbers in a processor die to identify the processor. Operating systems, programs, and chipsets may also have similar serial numbers to identify them. The serial numbers are typically unique, but be merely one of a large number of serial numbers so it would be highly unusual for another given processor, operating system or chipset to have the same number in a given situation.
PSNs can be used for authentication. For example, a client (user) can send a PSN to a vendor, which PSN is stored at the vendors site. Then, as part of a future transaction, a vendor can compare the stored PSN with the PSN currently received from the client. If there is a match, the transaction is allowed to continue.
However, allowing remote sites to store PSNs has raised privacy concerns. A solution to the privacy concern was provided by MIT computer science professor, Ronald Rivest, who suggested a way to have electronic commerce without providing unique identifiers. Hereinafter, it will be called the Rivest Scheme. Professor Rivest suggested, first, to eliminate the serial number from the CPU (processor). There is no serial number, and so it can't be queried for, or used as an identifier for the user of the CPU. Second, we give each CPU a unique secret key Ki. These secret keys may be 128-bit AES (Advanced Encryption Standard) keys, for example. No two chips have the same key Ki. The keys might be randomly generated by the CPU manufacturer. (It is assumed that the CPU manufacturer can be trusted not to reveal the key. However, the CPU chip could generate Ki and store it in nonvolatile memory without revealing it, or the variation on the following scheme could be devised.) There is no way for a user of the CPU to determine Ki; it can't be “read out” like a serial number.
Third, we give the CPU two new instructions: a “challenge” instruction and a “decrypt and compare” instruction. The “challenge” instruction causes the CPU to do a randomized encryption of a supplied challenge, and return the resulting ciphertext. The “decrypt and compare” instruction causes the chip to determine if two such ciphertexts could have been produced on the current CPU from the same challenge.
Random numbers are generated (e.g., by the chip from thermal noise). There may be a new instruction that causes the chip to return a register (or several registers) full of random bits.
The “challenge” instruction works as follows: the chip takes in a (say) 64-bit challenge c. It then generates a (say) 64-bit random number r, using the random number generation circuitry already announced. It then returns as the result of the challenge instruction the ciphertext:C(c,r)=AES(Ki,cr)
That is, it returns the encryption using the AES algorithm, under control of the key Ki, of the plaintext consisting of the concatenation of the challenge c with the random value r. (The first 64-bit half of the plaintext is c, the second 64-bit half of the plaintext is r.) The resulting 128-bit ciphertext C(c,r) is returned by the chip in an appropriate register or set of registers. The AES algorithm (not yet chosen) takes in 128-bit plaintext values and returns 128-bit ciphertext values, under control of a 128 (or 192 or 256)-bit key.
The “decrypt and compare” instruction takes in two values C1 and C2, and decrypts them using the chip's secret key Ki, to obtain (c1,r1) and (c2,r2), where C1=C(c1,r1) and C2=C(c2,r2). That is, C1 was produced (or could have been produced) by the challenge instruction on input challenge c1, and C2 has produced (or could have been produced) by the challenge instruction on input challenge c2. The chip returns “true” if c1=c2, and returns “false” otherwise.
Note again that the challenge instruction is randomized—it returns (with very high probability) a different result every time it is invoked, even if it is invoked with the same challenge. Thus, it is not usable as a way of producing a unique “serial number” for the chip. For example, the result of running the challenge instruction on input challenge “0” is always changing, so that it can't be used to identify the chip.
Although the scheme proposed here involves an encryption operation, it is not possible to use the chip to “get at” the underlying AES encryption and thus perform encryption efficiently. This is important if one must live with the current set of (defective, in my mind) export control laws on encryption. Chips with this scheme on them could presumably be exported without difficulty.
Now: how does a manufacturer use these instructions to provide software that can only be run on a particular CPU? The “serial number management” or “key management” process that we had before for dongles now becomes the following three-step process. First, the user runs a challenge instruction on some challenge on his CPU. The challenge might be supplied by the manufacturer, or chosen randomly by the user. Second, the user then informs the manufacturer of the challenge c and the response C1=C(c,r) that he obtained from the chip. Third, the manufacturer supplies the user with custom software that has embedded within it the ciphertext C1 and a test of the form: give the challenge c to the chip, apply the “challenge” instruction, and then use the “decrypt and compare” instruction to compare the result of the challenge instruction and C1. If the “decrypt and compare” instruction returns “true”, then proceed to execute the software. Otherwise, abort.
Software produced this way will only run on the CPU that produced the original response C1. This allows one to protect against software piracy, in that a manufacturer can produce software that runs on only one CPU. (The scheme extends easily to handle the case that the user owns multiple CPUs, by embedding multiple ciphertexts in the software, and seeing if any of them compare successfully.) Note that manufacturers cannot get together off-line to compare what they know, since all they have are ciphertexts produced using unknown keys for plaintexts of which they only know half. There is no way to “link” together different results of the “challenge” instruction, without using the very same chip on which those results were produced.